package basis.netease.easy;

import java.util.Arrays;

/**
 * 7-9 最小硬币个数
 * 假设现在有一堆硬币，其中有足够个1元硬币、足够个2元硬币和足够个5元硬币。现在需要用这些硬币凑出总价值为n元的钱，求最少需要多少枚硬币？
 * 输入格式:
 * 每一组输入为一行，代表需要凑出的钱的价值n。其中0<=n<=2147483647
 * 输出格式:
 * 对每一组输入，在一行中输出需要的硬币的值。如果不能凑出指定价值，请返回0。
 * 输入样例1:
 * 在这里给出一组输入。例如：
 * 0
 * 输出样例1:
 * 在这里给出相应的输出。例如：
 * 0
 * 输入样例2:
 * 在这里给出一组输入。例如：
 * 100
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * 20
 * 输入样例3:
 * 在这里给出一组输入。例如：
 * 14
 * 输出样例3:
 * 在这里给出相应的输出。例如：
 * 4
 */
public class Main_7 {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 2147481647;
        System.out.println(coinChange(coins, amount));
    }


    public static int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? 0 : dp[amount];
    }

}
